Finiteness Theorems for Graphs and Posets Obtained by Compositions
Identifieur interne : 00B366 ( Main/Exploration ); précédent : 00B365; suivant : 00B367Finiteness Theorems for Graphs and Posets Obtained by Compositions
Auteurs : Jens Gustedt [Allemagne]Source :
- Order [ 0167-8094 ] ; 1998-09-01.
English descriptors
- KwdEn :
Abstract
Abstract: We investigate classes of graphs and posets that admit decompositions to obtain or disprove finiteness results for obstruction sets. To do so we develop a theory of minimal infinite antichains that allows us to characterize such antichains by means of the set of elements below it. In particular we show that the following classes have infinite antichains with respect to the induced subgraph/poset relation: interval graphs and orders, N-free orders, orders with bounded decomposition width. On the other hand for orders with bounded decomposition diameter finiteness of all antichains is shown. As a consequence those classes with infinite antichains have undecidable hereditary properties whereas those with finite antichains have fast algorithms for all such properties.
Url:
DOI: 10.1023/A:1006209905006
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 002594
- to stream Istex, to step Curation: 002561
- to stream Istex, to step Checkpoint: 002598
- to stream Main, to step Merge: 00BA88
- to stream Main, to step Curation: 00B366
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Finiteness Theorems for Graphs and Posets Obtained by Compositions</title><author><name sortKey="Gustedt, Jens" sort="Gustedt, Jens" uniqKey="Gustedt J" first="Jens" last="Gustedt">Jens Gustedt</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:A109172EE9C72E9C235F4E74453C6D79E0EF351D</idno><date when="1998" year="1998">1998</date><idno type="doi">10.1023/A:1006209905006</idno><idno type="url">https://api.istex.fr/ark:/67375/VQC-S2L646RV-R/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">002594</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002594</idno><idno type="wicri:Area/Istex/Curation">002561</idno><idno type="wicri:Area/Istex/Checkpoint">002598</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002598</idno><idno type="wicri:doubleKey">0167-8094:1998:Gustedt J:finiteness:theorems:for</idno><idno type="wicri:Area/Main/Merge">00BA88</idno><idno type="wicri:Area/Main/Curation">00B366</idno><idno type="wicri:Area/Main/Exploration">00B366</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Finiteness Theorems for Graphs and Posets Obtained by Compositions</title><author><name sortKey="Gustedt, Jens" sort="Gustedt, Jens" uniqKey="Gustedt J" first="Jens" last="Gustedt">Jens Gustedt</name><affiliation wicri:level="4"><orgName type="university">Université technique de Berlin</orgName><country>Allemagne</country><placeName><settlement type="city">Berlin</settlement><region type="capital">Berlin</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author></analytic><monogr></monogr><series><title level="j">Order</title><title level="j" type="sub">A Journal on the Theory of Ordered Sets and its Applications</title><title level="j" type="abbrev">Order</title><idno type="ISSN">0167-8094</idno><idno type="eISSN">1572-9273</idno><imprint><publisher>Kluwer Academic Publishers</publisher><pubPlace>Dordrecht</pubPlace><date type="published" when="1998-09-01">1998-09-01</date><biblScope unit="volume">15</biblScope><biblScope unit="issue">3</biblScope><biblScope unit="page" from="203">203</biblScope><biblScope unit="page" to="220">220</biblScope></imprint><idno type="ISSN">0167-8094</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0167-8094</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>decidability</term><term>linear algorithms</term><term>suborder relation</term><term>substitution decomposition</term><term>well-quasi-ordering</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: We investigate classes of graphs and posets that admit decompositions to obtain or disprove finiteness results for obstruction sets. To do so we develop a theory of minimal infinite antichains that allows us to characterize such antichains by means of the set of elements below it. In particular we show that the following classes have infinite antichains with respect to the induced subgraph/poset relation: interval graphs and orders, N-free orders, orders with bounded decomposition width. On the other hand for orders with bounded decomposition diameter finiteness of all antichains is shown. As a consequence those classes with infinite antichains have undecidable hereditary properties whereas those with finite antichains have fast algorithms for all such properties.</div></front></TEI><affiliations><list><country><li>Allemagne</li></country><region><li>Berlin</li></region><settlement><li>Berlin</li></settlement><orgName><li>Université technique de Berlin</li></orgName></list><tree><country name="Allemagne"><region name="Berlin"><name sortKey="Gustedt, Jens" sort="Gustedt, Jens" uniqKey="Gustedt J" first="Jens" last="Gustedt">Jens Gustedt</name></region><name sortKey="Gustedt, Jens" sort="Gustedt, Jens" uniqKey="Gustedt J" first="Jens" last="Gustedt">Jens Gustedt</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00B366 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00B366 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:A109172EE9C72E9C235F4E74453C6D79E0EF351D
|texte= Finiteness Theorems for Graphs and Posets Obtained by Compositions
}}
| This area was generated with Dilib version V0.6.33. |  |